package com.gong.suanfa.mergeSort;

/**
 * @author GongChang
 * @version 1.0
 * @date 2021/6/8 0008 10:15
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {100,8,7,3,3,11,9,50,5};
        sort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void sort(int[] arr){
        int[] temp = new int[arr.length];

        sort(arr,0,arr.length-1,temp);
    }

    private static void sort(int[] arr, int l, int r, int[] temp) {
        if (l>=r){
            return;
        }
        int mid = l+((r-l)>>1);
        sort(arr,l,mid,temp);
        sort(arr,mid+1,r,temp);
        merge(arr,l,mid,r,temp);
    }

    private static void merge(int[] arr, int l, int mid, int r, int[] temp) {
        int i = l;
        int j = mid+1;
        int index = l;

        while (i <= mid && j<=r){
            if (arr[i] <= arr[j]){
                temp[index++] = arr[i];
                i++;
            }else {
                temp[index++] = arr[j];
                j++;
            }
        }
        while (i <= mid){
            temp[index++] = arr[i];
            i++;
        }
        while (j <= r){
            temp[index++] = arr[j];
            j++;
        }

        for (int k = l; k <= r; k++) {
            arr[k] = temp[k];
        }
    }
}
